package com.lw.leetcode.back.b;

import java.util.Arrays;

/**
 * back
 * 698. 划分为k个相等的子集
 *
 * @Author liw
 * @Date 2021/10/30 20:47
 * @Version 1.0
 */
public class CanPartitionKSubsets {

    public static void main(String[] args){
        CanPartitionKSubsets test = new CanPartitionKSubsets();

        //输出： True
//        int[] arr = {4, 3, 2, 3, 5, 2, 1};
//        int k = 5;

        // false
        int[] arr = {1739,5391,8247,236,5581,11,938,58,1884,823,686,1760,6498,6513,6316,2867};
        int k = 6;

        boolean b = test.canPartitionKSubsets(arr, k);
        System.out.println(b);
    }

    private int k ;
    private int n;
    private int[] arr;
    private int[] nums;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        Arrays.sort(nums);
        this. n = sum / k;
        this.k = k;
        this.arr = new int[k];
        this.nums = nums;
        arr[0] = nums[nums.length - 1];
        return find(nums.length - 2);
    }

    private boolean find (int index) {
        if (index == -1) {
            for (int value : arr) {
                if (value != n) {
                    return false;
                }
            }
            return true;
        }
        int value = nums[index];
        for (int i = 0; i < k; i++) {
            arr[i] += value;
            if (arr[i] <= n) {
                boolean b = find(index - 1);
                if (b) {
                    return true;
                }
            }
            arr[i] -= value;
        }
        return false;
    }

}
